原题地址：组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
回溯算法
与 组合总数 相比，这一题中的数字不是可能重复任意次数，它的重复次数将是该数字在candidates中本身出现的次数。其它过程与上一题是一样的：
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const combinationSum1 = function(candidates, target) {
candidates.sort((a, b) => a - b);
/**
* 求解从某一个位置开始，后面部分得到的和为sum的组合
* @param index 开始位置
* @param sum 要求的和
* @returns {[]|Array} 得到的结果集
*/
const combine = (index, sum) => {
// 数组已处理完，不会有新的结果出现，返回空数组
if (index === candidates.length) {
return [];
}
// 因为已经排过序，如果要处理的第一个数就比要得到的sum大，显然求和后是要大于sum的
if (candidates[index] > sum) {
return [];
}
let result = [];
// 求解当前数字的重复次数
let count = 1;
for (let i = index + 1; i < candidates.length; i ++) {
if (candidates[i] !== candidates[index]) {
break;
}
count ++;
}
// 当前数字最多只能重复count次
for (let i = 0; i <= count; i ++) {
// 得到了结果，将结果保存到result中
if (sum === i * candidates[index]) {
result.push(new Array(i).fill(candidates[index]));
} else {
// 将sum减去i次第一个数，然后递归求解后面的部分
// 注意这里是直接跳到后面第一个不重复的位置，因为重复的我们已经通过循环处理过了
let array = combine(index + count, sum - i * candidates[index]);
// 如果后面部分有解，就进行合并
if (array.length > 0) {
for (let j = 0; j < array.length; j ++) {
result.push(new Array(i).fill(candidates[index]).concat(array[j]));
}
}
}
}
return result;
};
// 从0开始求解
return combine(0, target);
};
测试：
let start = new Date();
const test = combinationSum1;
console.log(test([10,1,2,7,6,1,5], 8)); // [ [ 2, 6 ], [ 1, 7 ], [ 1, 2, 5 ], [ 1, 1, 6 ] ]
console.log(test([2,5,2,1,2], 5)); // [ [ 5 ], [ 1, 2, 2 ] ]
console.log(new Date().getTime() - start.getTime()); // 8
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 8,2019